Digital communications systems and digital storage systems are similar from the perspective of extracting the original (transmitted or stored) bits from the received signal or from the readback signal. In the case of communications channels, the digital information is transferred from one location to another location, but at the same time (perhaps with a small transmission delay), whereas in storage channels, the information is transferred from one time to a later time, but at the same location (e.g., on a magnetic disk). The goal in both cases is to retrieve the original bits as accurately as possible in the presence of impairments such as noise and inter-symbol interference (ISI).
One method for improving the accuracy of the retrieved digital information involves using error correcting codes (ECCs). ECCs typically use parity bits to introduce redundancy into the signal to encode it prior to transmission or storage. Such redundancy is subsequently used to decode the encoded information and correct bit errors. The ability to correct bit errors is known as error recovery performance.
A variety of different systems and techniques are known that rely on redundancy to encode and decode digital information. Some systems use an interleaver to generate and insert parity bits at various locations in the data stream. These systems are typically highly structured in the sense that they systematically generate and insert parity bits at various locations in the data stream in order to ensure that an error event will affect multiple parity equations. Increasing the number of parity equations that are affected by an error event increases the effectiveness of using redundancy. Such systems are usually relatively easy to implement in an integrated circuit (IC) and require a relatively small amount of area on the IC in which they are manufactured. One disadvantage of this type of system is that the highly structured manner in which bits are interleaved makes it very likely that a degenerate type of error event will occur that will exploit the structure of the system, thereby preventing the full potential of using redundancy from being realized.
Some encoders and decoders do not use an interleaver. In systems that do not use an interleaver, certain types of error events will always exploit the structure of the underlying parity equations. Such systems generally have relatively poor error recovery performance.
It is known that randomizing the underlying parity relationships (or equations) increases the number of parity equations that are affected by certain error events. Therefore, an interleaver that uses randomly defined parity relationships fully exploits redundancy and thus can provide very good error recovery performance. However, it is very difficult to achieve true randomness in manmade systems.
A need exists for a method and an apparatus for encoding and decoding digital information that more fully exploit the use of parity bit redundancy and which can be implemented relatively easily in an IC.